/**
 * @Question.Title: 前 K 个高频元素
 * @Question.No: 347
 * @Author: DQ
 * @Date: 2021-04-15 12:40:30
 * @Description: 
 */
//给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [1,1,1,2,2,3], k = 2
//输出: [1,2]
// 
//
// 示例 2: 
//
// 
//输入: nums = [1], k = 1
//输出: [1] 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 105 
// k 的取值范围是 [1, 数组中不相同的元素的个数] 
// 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的 
// 
//
// 
//
// 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。 
// Related Topics 堆 哈希表 
// 👍 727 👎 0

package dq.leetcode.editor.cn;

import java.util.*;
import java.util.stream.Collectors;

public class TopKFrequentElements {
    public static void main(String[] args) {
        Solution solution = new TopKFrequentElements().new Solution();
        int[] a = {1,1,1,2,2,3,3,3,3};
        System.out.println(Arrays.toString(solution.topKFrequent(a,2)));
    }
        //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i: nums){
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        int[] res = new int[k];
        int len = 0;
        List<Integer> collect = map.entrySet().stream()
                .sorted((a,b)->b.getValue()-a.getValue())
                .limit(k)
                .map(e->e.getKey())
                .collect(Collectors.toList());
        for(Integer i : collect){
            res[len++] = i;
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}